package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Queue;
import cn.edu.jxau.util.Stack;

/**
 * 有向图中基于深度优先搜索的顶点排序
 * @author 付大石
 */
public class DirectedDFSOrder {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(2, 3);
        g.addEdge(6, 0);
        g.addEdge(2, 0);
        g.addEdge(11, 12);
        g.addEdge(12, 9);
        g.addEdge(9, 10);
        g.addEdge(9, 11);
        g.addEdge(8, 9);
        g.addEdge(11, 4);
        g.addEdge(3, 5);
        g.addEdge(7, 8);
        g.addEdge(5, 4);
        g.addEdge(0, 5);
        g.addEdge(6, 4);
        g.addEdge(6, 9);
        g.addEdge(7, 6);
        g.addEdge(0, 1);
        DirectedDFSOrder order = new DirectedDFSOrder(g);
        for (int i : order.pre()) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : order.post()) {
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i : order.reversePost()) {
            System.out.print(i + " ");
        }
    }

    private boolean[] marked;
    /**
     * 前序
     */
    private Queue<Integer> pre;

    /**
     * 后序
     */
    private Queue<Integer> post;

    /**
     * 逆后序
     */
    private Stack<Integer> reversePost;

    public DirectedDFSOrder(DirectedGraph g) {
        
        marked = new boolean[g.v()];
        pre = new LinkedQueue<Integer>();
        post = new LinkedQueue<Integer>();
        reversePost = new LinkedStack<Integer>();
        for (int i = 0; i < g.v(); i++) {
            if (!marked[i]) {
                dfs(g, i);
            }
        }
    }

    private void dfs(DirectedGraph g, int v) {

        pre.enqueue(v);
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }

    public Iterable<Integer> reversePost() {
        return reversePost;
    }
}
